package gold.digger;

import gold.utils.InputUtil;

import java.util.Arrays;
import java.util.Comparator;
import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1996 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int numberOfWeakCharacters(int[][] properties) {
            // 求所有人的最大攻击力
            int maxAttack = 0;
            for (int[] p : properties) {
                maxAttack = Math.max(maxAttack, p[0]);
            }

            // 下面两步对攻击力做一个桶排序

            // attacks初始化为记录每一种攻击力对应的最大防御力
            // 同一个攻击力，可能不同人有不同的防御力，这里记录最大的
            int[] attacks = new int[maxAttack + 1];
            for (int[] p : properties) {
                attacks[p[0]] = Math.max(attacks[p[0]], p[1]);
            }

            // attacks修改为记录比当前攻击力大的人的最大防御力
            // 即使比当前攻击力对应的防御力低也要更新
            int maxDefence = 0;
            for (int i = maxAttack; i >= 0; i--) {
                int tmp = maxDefence;
                if (attacks[i] > maxDefence) {
                    maxDefence = attacks[i];
                }
                attacks[i] = tmp;
            }

            // 遍历，只要一个人的攻击力小于最大攻击力，且存在比他大的防御力，他就是弱角色
            int ans = 0;
            for (int[] p : properties) {
                if (p[0] < maxAttack && p[1] < attacks[p[0]]) {
                    ans++;
                }
            }
            return ans;
        }
    }


    class Solution_Time_Exceed {
        public int numberOfWeakCharacters(int[][] properties) {
            Arrays.sort(properties, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0] - o2[0];
                }
            });

            TreeMap<Integer, List<Integer>> cnt = new TreeMap<>();
            for (int i = 0; i < properties.length; i++) {
                if (!cnt.containsKey(properties[i][1])) cnt.put(properties[i][1], new ArrayList<>());
                cnt.get(properties[i][1]).add(i);
            }

            int sum = 0;
            for (int i = 0; i < properties.length - 1; i++) {
                Integer bigger = cnt.ceilingKey(properties[i][1] + 1);
                boolean curFindFlag = false;
                while (bigger != null && !curFindFlag) {
                    for (int idx : cnt.get(bigger)) {
                        if (properties[idx][0] > properties[i][0]) {
                            ++sum;
                            curFindFlag = true;
                            break;
                        }
                    }

                    bigger = cnt.ceilingKey(bigger + 1);
                }
            }

            return sum;
        }
    }

    public void run() {
        Solution solution = new Solution();

//        示例 1：
//
//        输入：properties = [[5,5],[6,3],[3,6]]
//        输出：0
//        解释：不存在攻击和防御都严格高于其他角色的角色。
//        示例 2：
//
//        输入：properties = [[2,2],[3,3]]
//        输出：1
//        解释：第一个角色是弱角色，因为第二个角色的攻击和防御严格大于该角色。
//        示例 3：
//
//        输入：properties = [[1,5],[10,4],[4,3]]
//        输出：1
//        解释：第三个角色是弱角色，因为第二个角色的攻击和防御严格大于该角色。

        //        输入：
        //[[7,7],[1,2],[9,7],[7,3],[3,10],[9,8],[8,10],[4,3],[1,5],[1,5]]
        //        输出：
        //        4
        //        预期结果：
        //        6

        System.out.println(solution.numberOfWeakCharacters(InputUtil.toDoubleIntegerArray("[[5,5],[6,3],[3,6]]")));
        System.out.println(solution.numberOfWeakCharacters(InputUtil.toDoubleIntegerArray("[[2,2],[3,3]]")));
        System.out.println(solution.numberOfWeakCharacters(InputUtil.toDoubleIntegerArray("[[1,5],[10,4],[4,3]]")));
        System.out.println(solution.numberOfWeakCharacters(InputUtil.toDoubleIntegerArray("[[7,7],[1,2],[9,7],[7,3],[3,10],[9,8],[8,10],[4,3],[1,5],[1,5]]")));

    }

    public static void main(String[] args) throws Exception {
        LC1996 an = new LC1996();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
